﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// inchwork 알고리즘
    /// O(n) 시간에 총합이 sum이 되는 최소 길이를 구함.
    /// </summary>
    public class Inchworm
    {
        private int[] arr;
        private int n;
        public Inchworm(int[] arr)
        {
            this.arr = arr;
            this.n = arr.Length;
        }
        public int Solve(int S)
        {
            int res = n + 1;
            int s = 0, t = 0, sum = 0;
            for (; ; )
            {
                while (t < n && sum < S)
                {
                    sum += arr[t++];
                }
                if (sum < S) break;
                res = Math.Min(res, t - s);
                sum -= arr[s++];
            }
            if (res > n)
            {
                res = 0;
            }
            Console.WriteLine(s + " " + t);
            return res;
        }
    }
}
